package BackTrack.万诺;

import 其他.DataStructure.TreeNode;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

import static MyUtils.MHUtils.*;

/*
 15分钟

 可以自由中间一段
    -> 就 main里 for前序遍历 每个当起点1次
 */
public class 路径总和II113_图很复杂 {
    @Test
    public void test() {
        TreeNode root = strToTree("5,4,8,11,null,13,4,7,2,null,null,5,1");
        List<List<Integer>> lists = pathSum(root, 22);
        System.out.println(lists);
    }

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> tmp = new ArrayList<>();
    int t;

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        t = targetSum;
        TreeNode cur = root;
        int faSum = 0;
        bT(cur,faSum);
        return res;
    }

    private void bT(TreeNode cur, int faSum) {
        if(cur.left==null && cur.right==null){
            tmp.add(cur.val);
            //中间bT扔掉
            tmp.remove(tmp.size()-1);

            tmp.add(cur.val);
            if(faSum+cur.val == t){
                res.add(new ArrayList<>(tmp));
            }
            tmp.remove(tmp.size()-1);
            return;
        }

        // 末1 用 lr!=null叶，要保证cur非n
        if(cur.left!=null) {
            tmp.add(cur.val);
            bT(cur.left, faSum + cur.val); // 同fasum
            tmp.remove(tmp.size() - 1);
        }
        if(cur.right!=null) {
            tmp.add(cur.val);
            bT(cur.right, faSum + cur.val); // 同fasum
            tmp.remove(tmp.size() - 1);
        }
    }
}
